home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln1285.arc / DADA.DOC < prev    next >
Text File  |  1986-02-27  |  16KB  |  319 lines
  1.  
  2.  
  3. This file offers additional comments, notes and hints on the Dada
  4. compiler given in DADA.PAS and described in Computer Language for
  5. December, 1985.
  6.  
  7.  1. Several of the types and variables that are defined globally in
  8.     DADA.PAS might better be declared as typed constants under Turbo
  9.     Pascal. They would then be local to the procedures that refer to
  10.     them and hence out of harm's way if some other procedure starts
  11.     meddling where it doesn't belong. They must be typed "constants"
  12.     rather than variables because they are static quantities: an error
  13.     message, for example, must retain its value between calls to the
  14.     error-listing routine. An added convenience of the Turbo typed
  15.     constants is that they can be initialized at the time they are
  16.     declared; thus the procedures InitKeywords and InitErrorList could
  17.     be discarded.
  18.  
  19.     I avoided using typed constants because they are not a feature of
  20.     standard Pascal.
  21.  
  22.     The following global variables (and their associated defined
  23.     types) might be made local in this way:
  24.  
  25.         OutLine, OutPoint, OutBuf
  26.         CH
  27.         LineCount
  28.         TypeSet, TFset, RelOpSet, AddOpSet, MultOpSet
  29.         CurrentScope
  30.         Keywords
  31.         ErrorList
  32.  
  33.  
  34.  2. For simplicity I have defined the symbol table as a linked linear
  35.     list of invariant records. Several improvements could be consid-
  36.     ered. A binary tree structure would speed up the compiler; a hash
  37.     table would go even faster. The only routines that would have to
  38.     be changed are Find, Declare and Blot. It hardly seems worth the
  39.     trouble, however; Dada is a toy language, and the compiler is
  40.     unlikely to be given long programs, where speed of compilation
  41.     would become an issue.
  42.  
  43.     If space rather than time is critical, a variant record could be
  44.     defined, with SymClass as the tag field. The VarType field is
  45.     needed only for variable entries and the Scope field only for
  46.     procedure entries. The savings, however, amount to only one byte
  47.     for VarType and two for Scope.
  48.  
  49.  
  50.  3. Doing a better job with errors is a lot of work. Stopping at the
  51.     first error is acceptable in a compiler that has a built-in
  52.     editor, where the position of the error can be indicated more or
  53.     less exactly on screen. In a batch-style compiler, the favored
  54.     strategy is to continue reading the source text, so that a single
  55.     compilation will in principle catch errors throughout the program.
  56.     The challenge is to recover from the first error well enough to
  57.     continue without issuing a Niagara of spurious error messages. The
  58.     Dada compiler is not capable of recovery. Removing the Halt state-
  59.     ment from the Error procedure will demonstrate this effectively.
  60.  
  61.  
  62.  4. The error-checking done here uses compiler directives peculiar to
  63.     Turbo Pascal. The main idea is that {$I-} allows the program to
  64.     continue after an input-output error, leaving an error code in the
  65.     system variable IoResult. If the operation is successful, IoResult
  66.     is zero. For other Pascal compilers equivalent services should be
  67.     available. A fuller and friendlier file-handling routine would
  68.     report the nature of the error, offer the user a second chance,
  69.     supply a default name for the output file, warn if an existing
  70.     file will be overwritten, etc.
  71.  
  72.     A more convenient way of getting the file names would be to
  73.     retrieve them from the the command line. I decided against doing
  74.     so because the methods of accessing command-line arguments vary
  75.     between Pascal compilers and between operating systems.
  76.  
  77.  
  78.  5. The simplicity of the scanner owes much to the simplicity of the
  79.     language being recognized, but it is also made possible in part by
  80.     delaying certain lexical decisions until the syntactic or even the
  81.     semantic phase of program analysis. The scanner returns the same
  82.     code (Ident) for all identifiers, whether they refer to variables
  83.     or to procedures. The distinction between variable and procedure
  84.     names is really a lexical one, but it is not made until the parser
  85.     looks up the identifier in the symbol table.
  86.  
  87.     Postponing this part of the lexical analysis allows the scanner to
  88.     operate without either lookahead of backtracking. At any moment,
  89.     the scanner knows only the current input symbol (the content of
  90.     variable CH), and once it has consumed that character it can never
  91.     go back to read it again.
  92.  
  93.     In many compilers the scanner has broader responsibilities and is
  94.     consequently more complex. For example, if the scanner (rather
  95.     than the parser) installs identifiers in the symbol table, they
  96.     must be classified unambiguously at the outset. In Dada this might
  97.     be done by looking ahead, after finding an identifier, to see if
  98.     it is followed by an assignment operator, which would imply that
  99.     the identifier is (or ought to be) a variable name. If the
  100.     assignment operator were not found, the pointer to the input
  101.     stream would have to be backed up to the character immediately
  102.     following the identifier.
  103.  
  104.  
  105.  6. The organization of the symbol table and the three routines that
  106.     access the table are based on the most-closely-nested rule of
  107.     Pascal and other block-structured languages. Since the table is
  108.     searched from youngest to oldest, a call to Find(IdentifierName)
  109.     will always return a pointer to the most recent entry that matches
  110.     IdentifierName. This allows the compiler to distinguish between
  111.     identifiers that have the same name but differ in scope.
  112.  
  113.     Suppose a Dada program makes the following declarations, causing
  114.     the parser to make the symbol-table calls shown. For each line the
  115.     value of CurrentScope is given in brackets:
  116.  
  117.         procedure Proc1;            [1] { Declare(Proc1)   }
  118.             procedure Proc1A;       [2] { Declare(Proc1A)  }
  119.             begin                   [3]
  120.             end;                    [2] { Blot             }
  121.             procedure Proc1B;       [2] { Declare(Proc1B)  }
  122.                 procedure Proc1Ba;  [3] { Declare(Proc1Ba) }
  123.                 begin               [4]
  124.                 end;                [3] { Blot             }
  125.             begin                   [3]
  126.             end;                    [2] { Blot             }
  127.         begin                       [2]
  128.         end;                        [1] { Blot             }
  129.         procedure Proc2;            [1] { Declare(Proc2)   }
  130.         begin                       [2]
  131.         end;                        [1] { Blot             }
  132.  
  133.     The corresponding symbol-table entries would be built up by
  134.     Declare and subsequently eliminated by Blot in the following
  135.     order:
  136.                     NAME    SCOPE    NEXT       CURRENTSCOPE
  137.  
  138.     FirstSym -->    Proc1     1     ^<earlier>        1
  139.  
  140.                     Proc1     1     ^<earlier>
  141.     FirstSym -->    Proc1A    2     ^Proc1            2
  142.  
  143.                     Proc1     1     ^<earlier>
  144.                     Proc1A    2     ^Proc1
  145.     FirstSym -->    Proc1B    2     ^Proc1A           2
  146.  
  147.                     Proc1     1     ^<earlier>
  148.                     Proc1A    2     ^Proc1
  149.                     Proc1B    2     ^Proc1A
  150.     FirstSym -->    Proc1Ba   3     ^Proc1B           3
  151.  
  152.                     Proc1     1     ^<earlier>
  153.                     Proc1A    2     ^Proc1
  154.     FirstSym -->    Proc1B    2     ^Proc1A           2
  155.  
  156.                     Proc1     1     ^<earlier>
  157.     FirstSym -->    Proc2     1     ^Proc1            1
  158.  
  159.     The appending of a symbol to the table by Declare is straight-
  160.     forward. A new instance of the record structure is created, then
  161.     the Next field of the new record is made to point to the current
  162.     FirstSym, and finally FirstSym is adjusted to point to the new
  163.     record. Thus each new record is put at the "front" of the list.
  164.  
  165.     The culling of old symbols by Blot is not quite as obvious. Each
  166.     name must be made inaccessible once the program passes beyond the
  167.     scope of that name. In the fragment above, for example, Proc2
  168.     should not be able to call Proc1A, Proc1B or Proc1Ba because those
  169.     procedures are local to Proc1. In Dada this is accomplished by
  170.     eradicating the symbol-table entry for a procedure once the "end"
  171.     that marks the limit of its scope is reached. The global variable
  172.     CurrentScope is incremented each time a block is entered; Blot
  173.     decrements CurrentScope and then works up the list, unlinking any
  174.     entries whose scope is numerically greater than CurrentScope.
  175.  
  176.     Two further notes are needed. First, observe that "end" can appear
  177.     in two contexts in Dada (or Pascal): at the end of a block or at
  178.     the end of a compound statement. Blot must be called only on
  179.     exiting a block, not on completing a compound statement. Second,
  180.     the technique of making symbol-table entries inaccessible by
  181.     simply erasing them may not work in more elaborate compilers. If
  182.     there is an optimizing pass, for example, it will probably need to
  183.     consult the symbol table. The proper approach then is to include a
  184.     flag field in the record, so that a procedure like Blot can mark a
  185.     name as hidden without destroying the entry. This also allows
  186.     better error messages--"Variable referenced outside its scope"
  187.     rather than "Undeclared variable."
  188.  
  189.  
  190.  7. Forth systems vary a good deal, not only in the language they
  191.     accept but also in the file format they expect. The code generator
  192.     given here creates "screen" files made up of 1,024-byte blocks.
  193.     Each such block is conventionally viewed as a screen of 16 lines
  194.     with 64 characters per line. There are no end-of-line delimiters;
  195.     every character position that is not occupied by Forth text is
  196.     filled with an ASCII blank. Input in this form should be accept-
  197.     able to many Forth systems, provided they use the operating-system
  198.     disk format. The published routines were tested with versions of
  199.     PC/FORTH, from Laboratory Microsystems, Inc.
  200.  
  201.     The plasticity and mutability of Forth itself raises other
  202.     problems. The various standards (fig-Forth, Forth-79, Forth-83)
  203.     differ appreciably, and there are differences even among systems
  204.     that are meant to conform to the same standard. I have tried to
  205.     confine myself to Forth words that are common to all systems, but
  206.     no doubt incompatibilities will turn up. The code generator can
  207.     produce the following Forth words:
  208.  
  209.     (   )   FORTH   DEFINITIONS   DECIMAL   CONSTANT   VARIABLE   :
  210.     ;   ;S   -->   @   !   .   CR   MINUS   0=   =   <   >   DUP
  211.     DROP   SWAP   OVER   KEY   EMIT   IF   ELSE   THEN   BEGIN   WHILE
  212.     REPEAT   OR   AND   -   *   +   /   MOD
  213.  
  214.     In addition, the following synonyms are defined in the header that
  215.     precedes every program:
  216.       1 CONSTANT TRUE
  217.       0 CONSTANT FALSE
  218.       : NEGATE MINUS ;
  219.       : NOT 0= ;
  220.       : <> = NOT ;
  221.       : >= < NOT ;
  222.       : <= > NOT ;
  223.  
  224.     If any of this will make your Forth system choke, change it, or
  225.     add definitions to the header to provide compatibility.
  226.  
  227.  
  228.  8. The Dada compiler employs the parsing technique called recursive
  229.     descent, which directly reflects the recursive definition of the
  230.     language syntax. The program itself also illustrates this
  231.     structure: the routines are nested so that each one is accessible
  232.     only to the nest-higher-level routine that calls it. The overall
  233.     structure looks like this:
  234.  
  235.     ParseProgram
  236.       ParseVariables
  237.       ParseBlock
  238.         ParseStatement
  239.           ParseExpression
  240.             ParseSimpleExpr
  241.               ParseTerm
  242.                 ParseSignedFactor
  243.                   ParseFactor
  244.  
  245.     Thus to recognize a program the parser must find variable
  246.     declarations and a block; in recognizing a block it tries to
  247.     resolve the input stream into statements, and so on.
  248.  
  249.     The recursive structure takes care of much of the bookkeeping that
  250.     would otherwise burden the program (and the programmer). This is
  251.     clearest in the parsing of expressions. In Forth as well as in
  252.     most machine languages expressions must be given in postfix
  253.     notation, whereas Dada and other "algebraic" languages use infix
  254.     notation. Making the conversion requires maintaining a stack of
  255.     pending operators. For example, the infix expression 3 * (4 + 5)
  256.     must be converted to the postfix 3 4 5 + *; to do so the operators
  257.     "+" and "*" must be stacked until both their operands have been
  258.     read from the input stream.
  259.  
  260.     Examination of the parsing routines reveals no stack-management
  261.     apparatus. How is it done? The stack employed is the return stack
  262.     created by the storage-allocation subsystem of the Pascal com-
  263.     piler. Although HoldMultOp, for example, is defined as a single
  264.     variable, the executing program can actually create many instances
  265.     of it. Every time ParseTerm is called, a new instance of
  266.     HoldMultOp is pushed onto the return stack.
  267.  
  268.     One final note on the parser: Just as the scanner can see only the
  269.     current character in the source file, the parser has access only
  270.     to the current token in the input stream. There is no explicit
  271.     lookahead or backtracking. Whereas the scanner really does its
  272.     analysis one symbol at a time, however, the parser saves a great
  273.     deal of information on its (hidden) stack. Indeed, the first
  274.     identifier in a program--the name of the program itself--is saved
  275.     until the main block at the very end of the program is reached.
  276.  
  277.  
  278.  9. The type checking done in DADA.PAS is not quite complete. The
  279.     operators are classified as RelOps, AddOps and MultOps according
  280.     to their precedence relations--multiplication must be done before
  281.     addition and addition before comparison. There is another dimen-
  282.     sion of classification, however, that the compiler ignores. Log-
  283.     ical OR has the same precedence as multiplication, and logical AND
  284.     is at the same level as addition, but the logical and arithmetic
  285.     operations properly apply to values of different types. As the
  286.     program stands, the compiler makes certain that the two operands
  287.     in each operation have the same type, but there is no assurance
  288.     the operator is appropriate. Thus "6 + FALSE" would generate an
  289.     error, but "6 AND 7" or "TRUE * FALSE" would pass without com-
  290.     plaint. Because Forth encodes boolean values as integers, such
  291.     expressions will also execute without causing a run-time error.
  292.  
  293.     The remedy is straightforward, although it makes the code somewhat
  294.     bulkier. ParseSimpleExpr and ParseTerm must be made to analyze
  295.     logical and arithmetic expressions separately. Both operands of
  296.     AND and OR must be boolean values, and both operands of +, -, *
  297.     and / must be integers. In ParseExpression some decisions need to
  298.     be made. Boolean values can surely be compared for equality, but
  299.     is "TRUE > FALSE" a meaningful expression? All this becomes still
  300.     more complicated when additional data types, such as strings and
  301.     characters, are introduced.
  302.  
  303.  
  304. 10. There is a minor discrepancy between grammar and compiler in the
  305.     function ParseStatement. The grammar for Dada, following that for
  306.     Pascal, defines the semicolon as a statement separator, not a
  307.     statement terminator. Hence the proper syntax of a compound state-
  308.     ment is:    begin
  309.                   A := B;
  310.                   B := C;
  311.                   C := D
  312.                 end
  313.     where there is no semicolon following the last simple statement
  314.     and preceding the "end". It's hard enough, however, remembering
  315.     where to put semicolons without also remembering special rules
  316.     about where not to put them. Many Pascal compilers therefore make
  317.     the final semicolon optional--unneeded but harmless if present.
  318.     The same policy is adopted in Dada.
  319.